#!/bin/env python

import sys

class Symbol:
    def __init__(self, type, value):
        self.type  = type
        self.value = value
    def __repr__(self       ): return repr(self.type) + ":" + repr(self.value)
    def represents(self): return [self]
    def get(self): return self.value

class SymbolType:
    def __init__(self, value): self.value = value
    def create(self, value): return Symbol(self, value)
    def __repr__(self       ): return repr(self.value)
    def represents(self): return [self]

class SymbolInstance(SymbolType):
    def __init__(self, value):
        SymbolType.__init__(self, value)
        self.symbol = Symbol(self, value)
    def create(self, value): return self.symbol

SymbolType.tEnd = SymbolInstance("tEnd")

class SymbolClass(SymbolType):
    def __init__(self, value, *symbols):
        SymbolType.__init__(self, value)
        self.symbols = symbols

    def represents(self): return self.symbols

class SymbolString:
    def __init__(self, *symbols):
        self.symbols = list(symbols)
        self.symbols.append(SymbolType.tEnd)
        self.length  = self.symbols.index(SymbolType.tEnd)

    def __repr__(self       ): return repr(self.symbols)
    def suffix  (self, p, *i): return SymbolString(*(self.symbols[p:self.length] + list(i)))

class Rule:
    def __init__(self, left, right, f = None):
        self.l = left
        self.r = SymbolString(*right)
        self.f = f

    def __repr__   (self   ): return repr(self.l) + " >> " + repr(self.r) # + " & " + repr(self.f)
    def __getitem__(self, i): return self.r.symbols[i]
    def left       (self   ): return self.l
    def right      (self   ): return self.r

    def apply(self, stack, context):
        args = [context]
        for i in xrange(self.r.length): args.insert(1, stack.pop().symbol.get())
        print >> sys.stderr, self
        return self.l.create(self.f(*args))

def N(*syms ): return set(syms)
def T(*syms ): return set(syms)
def I(*syms ): return set(syms)
def P(*rules): return rules

class Grammar:
    nAugmented = SymbolType("nAugmented")
    def __init__(self, p, s, i = set()): (self.p, self.s, self.i) = (p, s, i)
    def augment(self): return Grammar(self.p + (Rule(self.nAugmented, [self.s], None),), self.nAugmented, self.i)
    def ignore(self) : return self.i
    def rules(self)  : return self.p

class GrammarProcessor:
    empty = []
    def __init__(self, grammar):
        self.P = {}
        self.F = {}
        self.p = grammar.p
        for r in grammar.p: self.P.setdefault(r.left(), []).append(r)
        self.P[None] = self.P[grammar.s]
        self.ign = grammar.ignore()

    def first(self, s):
        if s in self.F: return self.F[s]
        if s not in self.P: self.F[s] = set(s.represents())
        else:
            self.F[s] = set()
            for r in self.P[s]:
                for sr in r[0].represents(): self.F[s] |= self.first(sr)
        return self.F[s]

    def FIRST(self, aSymbolString):
        f = set()
        for sc in aSymbolString.symbols:
            nf = set()
            for s in sc.represents(): nf |= self.first(s)
            f |= nf
            if not SymbolType.tEnd in nf: break
        return f

    def isTerminal(self, s)     : return s not in self.P
    def rulesFor(self, s = None): return self.P.get(s, self.empty)
    def ignore(self            ): return self.ign
